package day190820;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/8/20 下午 04:39
 */
public class NumMatrix {
    private int[][] dpMap;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0) {
            return;
        }
        int m = matrix.length, n = matrix[0].length;
        dpMap = new int[m][n];
        dpMap[0][0] = matrix[0][0];
        for (int i = 1; i < m; i++) {
            dpMap[i][0] = dpMap[i - 1][0] + matrix[i][0];
        }
        for (int i = 1; i < n; i++) {
            dpMap[0][i] = dpMap[0][i - 1] + matrix[0][i];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dpMap[i][j] = dpMap[i - 1][j] + dpMap[i][j - 1] - dpMap[i - 1][j - 1] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (row1 == 0 && col1 > 0) {
            return dpMap[row2][col2] - dpMap[row1][col1 - 1];
        }
        if (row1 > 0 && col1 == 0) {
            return dpMap[row2][col2] - dpMap[row1 - 1][col1];
        }
        if (row1 == 0 && col1 == 0) {
            return dpMap[row2][col2];
        }
        return dpMap[row2][col2] - dpMap[row1 - 1][col1 - 1];
    }

    public static void main(String[] args) {
        int[][] matrix = {{3, 0, 1, 4, 2},
                        {5, 6, 3, 2, 1},
                        {1, 2, 0, 1, 5},
                        {4, 1, 0, 1, 7},
                        {1, 0, 3, 0, 5}};
        NumMatrix matrix1 = new NumMatrix(matrix);
    }

}
